#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

//f(n) = n + f(n - 1) (n > 1)
//f(1) = 1
int GetSum(int n){
    if(n == 1){
        return 1;
    }
    return n + GetSum(n - 1);
}


/**
 * 递归求和
 */
void Test01(){
    cout << "1 + 2 + ... + 100 = " << GetSum(100) << endl;
}

// f(n) = n * f(n - 1) (n > 1)
// f(1) = 1
int GetFactorial(int n){
    if(n == 1){
        return 1;
    }
    return n * GetFactorial(n - 1);
}


/**
 * 递归求阶乘
 */
void Test02(){
    cout << "1 * 2 * ... * 10 = " << GetFactorial(10) << endl;
}

/**
 * f(n) = max(f(left), f(right)) (left < right)
 * f(left) = nums[left]
 * f(right) = nums[right]
 * 
 */
int GetMax(vector<int>& nums, int left, int right) {
    if (left == right) {
        return nums[left];
    }
    int mid = (right + left) / 2;
    int leftMax = GetMax(nums, left, mid);
    int rightMax = GetMax(nums, mid + 1, right);
    return max(leftMax, rightMax);
}


/**
 * 递归求最大值
 */
void Test03(){
    vector<int> nums = {1, 3, 5, 7, 9, 2, 4, 6, 8, 0};
    int maxVal = GetMax(nums, 0, nums.size() - 1);
    cout << "最大值为: " << maxVal << endl;
}

// f(n) = f(n - 1) + f(n - 2)
// f(1) = 1
// f(2) = 2
int Fib(int n){
    if (n <= 2) {
        return n;
    }
    return Fib(n - 1) + Fib(n - 2);
}


/**
 * 递归求fibonacci数列
 */
void Test04(){
    int n = 10; // 求第10个Fibonacci数
    cout << "Fibonacci(" << n << ") = " << Fib(n) << endl;
}

// f(n) = 1 + 1 / f(n - 1)
// f(1) = 1
double GetGoldenRatio(int n) {
    if (n == 1) {
        return 1.0;
    }
    return 1.0 + 1.0 / GetGoldenRatio(n - 1);
}


/**
 * 递归求黄金比
 */
void Test05(){
    int n = 100; // 求第10个黄金比
    cout << "黄金比(" << n << ") = " << GetGoldenRatio(n) << endl;
}

/**
 * x^2 + 2x - 1 = 0
 * x + 2 - 1/x = 0
 * 一个解： x +2 = 1/x ==> x = 1/(x + 2)
 * 另一个解：x = -2 + 1/x
 */

double GetX1(int n){
    if (n == 1){
        return 1.0;
    }

    return 1/(2 + GetX1(n - 1));
}

double GetX2(int n){
    if (n == 1){
        return 1.0;
    }

    return -2 + 1/GetX2(n - 1);
}


/**
 * 递归求1+sqrt(2)
 */
void Test06(){
    int n = 100;
    cout << GetX1(n) << endl;
    // cout << GetX2(n) << endl;
}

// f(n, k) = f(n - 1, k - 1) + f(n - 1, k)
// f(n, 0) = 1
// f(n, n) = 1
int C(int n, int k){
    if (k == 0 || k == n) {
        return 1;
    }
    return C(n - 1, k - 1) + C(n - 1, k);
}

/**
 * 递归求组合数
 */
void Test07(){
    int n=5, k=2;
    cout << C(n, k) << endl;
}


// f(a, b) = b == 0 ? a : f(b, a % b)
int Gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    return Gcd(b, a % b);
}

/**
 * 递归求最大公约数
 */
void Test08(){
    int a = 514, b = 114;
    cout << "GCD(" << a << ", " << b << ") = " << Gcd(a, b) << endl;
}


double F(double n){
    if (n == 1000){
        return n;
    }
    return n*sqrt(F(n+1)+1);
}


/**
 * 递归求3
 */
void Test09(){
    int n = 1;
    cout  << F(n) << endl;
}


// f(n) = 2 * f(n - 1) + 1
// f(1) = 1
int T(int n){
    if (n == 1) {
        return 1;
    }
    return 2*T(n-1) + 1;
}


/**
 * 递归求幂
 */
void Test10(){
    int n = 10;
    cout << T(n) << endl;

}


/**
 * 递归的基本使用
 */
int main(){

    //Test01();

    // Test03();

    // Test05();

    // Test06();

    Test07();

    // Test08();

    // Test09();

    // Test10();


  

    return 0;
}